package psn.zjk.career.interview.algorithm;

import java.util.*;

/**
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 * <p>
 * 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
 *
 * @USER zero
 * @DATETIME 2021/4/11 12:05
 */
public class LeetCode264 {

    //后面的丑数=前面的丑数*丑数,思路：最小堆,优先队列，每次移除堆顶
    public int nthUglyNumber(int n) {
        int count = 0;
        TreeSet<Long> integers = new TreeSet<>();
//        PriorityQueue<Integer> x = new PriorityQueue<>();
        integers.add(1L);
        while (count < n) {
            Long first = integers.first();
            integers.remove(first);
            count++;
            if (count == n)
                return first.intValue();
            add(integers, first * 2);
            add(integers, first * 3);
            add(integers, first * 5);
        }
        return 0;
    }

    private void add(TreeSet<Long> integers, Long first) {
        if (first > 0) {
            integers.add(first);
        }
    }

    public int dpWay(int n) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        //
        int p2, p3, p5;
        p2 = p3 = p5 = 0;
        for (int i = 1; i < n; ++i) {
            //选出最小的
            Integer min = Math.min(Math.min(2*list.get(p2), 3*list.get(p3)), 5*list.get(p5));
            list.add(min);
            //2倍数中最小的丑数已存在，则指针p2右移；
            if (min == 2 * list.get(p2)) {
                ++p2;
            }
            if (min == 3 * list.get(p3)) {
                ++p3;
            }
            if (min == 5 * list.get(p5)) {
                ++p5;
            }
        }
        return list.get(n-1);
    }


    public static void main(String[] args) {

        //1399680000
        System.out.println(new LeetCode264().dpWay(1600));
    }

}
